package 中等.数学;

/**
 * 给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [2,3,4] -> 2 / 3 / 4 。
 * <p>
 * 但是，你可以在任意位置添加任意数目的括号，来改变算数的优
 * 先级。你需要找出怎么添加括号，才能得到最大的结果，并且返
 * 回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/optimal-division
 */
public class 最优除法_553 {

    public static void main(String[] args) {

    }

    /**
     * 数学+贪心
     * 注意：数组中每个元素的大小都在 [2, 1000] 之间，意味着两个数相除必然变小
     * 分子/分母，想要获取最大值，分子尽可能的大，分母尽可能的小
     * 而每除以一个数必然变小，那么分子的最大值即为nums[0]
     * 证明：分母最小为nums[1]/nums[2]/nums[3]/...
     * 如果先后面两个数相除，nums[1]/(nums[2]/nums[3])
     * 正常除                (nums[1]/nums[2])/nums[3]
     * 想要最小值，分子尽可能小，分母尽可能大，
     * 因为分子  nums[1]>nums[1]/nums[2]
     * 并且分母  nums[2]/nums[3]<nums[3]
     * 不加任何括号会得到最小值
     *
     * @param nums
     * @return
     */
    public String optimalDivision(int[] nums) {
        if (nums.length == 1) {
            return String.valueOf(nums[0]);
        }
        if (nums.length == 2) {
            return nums[0] + "/" + nums[1];
        }
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(nums[0]).append("/(");
        for (int i = 1; i < nums.length - 1; i++) {  //去除收尾
            stringBuilder.append(nums[i]).append("/");
        }
        stringBuilder.append(nums[nums.length - 1]).append(")");
        return stringBuilder.toString();
    }

}
